// Created by WXX on 2022/1/4 19:34
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：4 ms, 在所有 C++ 提交中击败了100.00%的用户
 * 内存消耗：5.8 MB, 在所有 C++ 提交中击败了59.67%的用户
 */
class Solution {
public:
    string week[7] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
    int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    bool is_leap(int year) {
        return year % 4 == 0 && year % 100 || year % 400 == 0;
    }

    string dayOfTheWeek(int day, int month, int year) {
        int start = 4;  // 1971.1.1  -->  周五
        int a = 1971, b = 1, c = 1;
        while (a != year || b != month || c != day) {
            c++;
            if (c > months[b] + (b == 2 ? is_leap(a) : 0)) {
                b++, c = 1;
                if (b > 12) a++, b = 1;
            }
            start = (start + 1) % 7;
        }
        return week[start];
    }
};

int main() {

    cout << Solution().dayOfTheWeek(31, 8, 2019) << endl;  // Saturday

    return 0;
}
